﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{





    public class Solution4
    {
        public double FindMedianSortedArrays2(int[] nums1, int[] nums2)
        {


            int len1 = nums1.Length;
            int len2 = nums2.Length;
            int len = len1 + len2;

            //如果len是奇数，k1==k2,会求两个一样的
            int k1 = (len + 1) / 2;
            int k2 = (len + 2) / 2;
            //如果len是偶数数，k1+1==k2,会求两个挨着的
            int target1 = DFS(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k1);
            int target2 = DFS(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k2);


            return (target1 + target2) * 0.5;
        }


        int DFS(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k)
        {
            int len1 = end1 - start1 + 1;
            int len2 = end2 - start2 + 1;
            int midNum = k / 2;

            if (len1 > len2)
            {
                return DFS(nums2, start2, end2, nums1, start1, end1, k);
            }
            if (len1 == 0)//有长度为0的话，返回另一个
            {
                return nums2[start2 + k - 1];
            }

            if (k == 1)//返回较小值
            {

                return Math.Min(nums2[start2], nums1[start1]);
            }





            int mid1 = start1 + Math.Min(midNum, len1) - 1;  //剩下的长度可能小于k/2,如果这一半小的话，会把小的长度（Len1）减去就结果就在剩下的
            int mid2 = start2 + Math.Min(midNum, len2) - 1;
            if (nums1[mid1] < nums2[mid2])
            {//舍弃num1的左边
                k = k - (mid1 - start1 + 1);
                start1 = mid1 + 1;


            }
            else
            {
                k = k - (mid2 - start2 + 1);
                start2 = mid2 + 1;
            }
            return DFS(nums1, start1, end1, nums2, start2, end2, k);
        }



        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {


            int len1 = nums1.Length;
            int len2 = nums2.Length;

            if (len1 > len2)
            {
                return FindMedianSortedArrays(nums2,nums1); 
            }

            //左半等于右半，i+j=len1-i+len2-j
            //
            int iLeft = 0;
            int iRight = nums1.Length;


            while (iLeft < iRight)

            {
                int i = (iRight + iLeft) / 2;
                Console.WriteLine(i);
                int j = (len1 + len2 + 1) / 2 - i;
                Console.WriteLine(j);
                if (i != 0 && j != len2 && nums1[i - 1] > nums2[j])
                {

                    iRight = i - 1;

                }
                else if (i != len1 && j != 0 && nums1[i] < nums2[j - 1])
                {

                    iLeft = i + 1;

                }
                else
                {

                    //代码保证，一开始分割的时候，左右数量相等，每次左边加1 ，右边也减1，
                    //所以某个数组左边为空的时候，另一个数组的左边肯定是一半
                    Console.WriteLine("准备输出");
                    int maxLeft = 0;
                    if (i == 0)//空一个
                    {
                        maxLeft = nums2[j - 1];

                    }
                    else if (j == 0)
                    {
                        maxLeft = nums1[i - 1];
                    }
                    else
                    {
                        maxLeft = Math.Max(nums1[i - 1], nums2[j - 1]);
                    }

                    if ((len1 + len2) % 2 == 1)//奇数
                    {

                        return maxLeft;
                    }

                    int minRight = 0;

                    if (i == len1)
                    {
                        minRight = nums2[j];
                    }
                    else if (j == len2)
                    {
                        minRight = nums1[i];
                    }
                    else
                    {
                        minRight = Math.Min(nums1[i], nums2[j]);

                    }

                    return (minRight + maxLeft) * 0.5;

                }



            }



            return 0.0;
        }
    }


    class Program4
    {


        static void Main4(string[] args)
        {
            Solution4 s = new Solution4();

            int[] nums1 = [5,6];
            int[] nums2 = [1,2,3, 4, 7,8,9];
           double res= s.FindMedianSortedArrays(nums1, nums2);
            Console.WriteLine(res);

        }
    }
}
